A digital filter structure usually comprises delay registers, multipliers and adders. In an IIR filter, these components are usually arranged in a feedback branch. Depending on the system requirements for digital filters, the number of required multiplication processings may vary drastically.
When implementing digital filters, it is desired and often necessary to reduce implementation costs as much as possible. The performance of the digital filter depends on the architectures used for implementation, i.e. DSP (Digital Signal Processor), ASIC (Application Specific Integrated Circuit) or FPGA (Field Programmable Gate Array).
FPGAs play an increasingly important role in digital signal processing systems. They are widely used both for smaller designs in commercial products and in larger prototypes used for system evaluations. Their advantage compared to ASICs is the fast implementation of a circuit design into a hardware arrangement and the low price at low volumes.
However, since the FPGA architecture sets constraints on the size of the design, it is required to keep the design as small as possible, such that the circuit can be implemented as an FPGA device. Moreover, the FPGA architecture sets constraints on the maximum clock frequency, such that additional implementation techniques have to be chosen for FPGAs in order to achieve high speed circuits.
A digital filter can be implemented as an FIR filter or as an IIR filter. According to the known structure of a digital FIR filter, sampled input data obtained from a filter input signal are delayed by a sampling period or a multiple thereof. The length or multiple of the maximum delay period in relation to the sample period used for generating the sampled input data defines the order of the digital filter. Each delayed sample data corresponding to a predetermined delay period is weighted by a corresponding filter coefficient which defines the type and shape of the filter.
Assuming an incoming data x(n) filtered by a filter having the coefficients b0, b1, . . . , bK, the output data is expressed by the following equation (1):                               y          ⁡                      (            n            )                          =                              ∑                          i              =              0                        K                    ⁢                                    b              i                        ⁢                          x              ⁡                              (                                  n                  -                  i                                )                                                                        (        1        )            
Thus, (K+1) multiplications and K additions are necessary in order to calculate the output signal y(n), such that a large chip area and a high power consumption is required.
A known approach to reduce the required chip size is to use a time-shared multiplication processing. Therein, the input data x(n) is propagated through a delay line and the filter coefficients bi are stored in a memory. Then, the corresponding delayed input values x(n−i) and bi are successively multiplied with each other in a time serial manner and the results are accumulated in an accumulator. Thus, only one multiplier is required for the whole digital filter processing. However, this approach requires a multiplication processing which has to be carried out much faster than the arrival of the data at the filter input. Thus, in case of high data speed applications, problems arise due to the physical limitations of the devices. Consequently, the implementation of a time-shared multiplier may not be feasible.
Furthermore, FIR filters can be implemented in an efficient manner into an FPGA architecture using the so-called distributed arithmetics (DA) approach.
In this case, the multiplication is actually not carried out, but the result is looked up in a ROM look-up table used for storing the results of the multiplications. In DA filters, the input signal is represented in binary form in the 2's complement which is represented by the following equation (2):                               x          ⁡                      (                          n              -              i                        )                          =                              -                                          x                0                            ⁡                              (                                  n                  -                  i                                )                                              +                                    ∑                              b                =                1                                            B                -                1                                      ⁢                                                            x                  b                                ⁡                                  (                                      n                    -                    i                                    )                                            ·                              2                                  -                  b                                                                                        (        2        )            
Wherein xb(n−i) denotes a binary variable and b the bit position of the binary variable within the input data x(n−i).
If this equation (2) is inserted into the equation (1) the output signal is expressed as follows:                                                                         y                ⁡                                  (                  n                  )                                            =                            ⁢                                                                    -                                                                  ∑                                                  i                          =                          1                                                K                                            ⁢                                                                                                    x                            0                                                    ⁡                                                      (                                                          n                              -                              i                                                        )                                                                          ⁢                                                  b                          i                                                                                                      +                                                            ∑                                              i                        =                        1                                            K                                        ⁢                                                                  ∑                                                  b                          =                          1                                                                          B                          -                          1                                                                    ⁢                                                                                                    x                            b                                                    ⁡                                                      (                                                          n                              -                              i                                                        )                                                                          ⁢                                                  b                          i                                                ⁢                                                  2                                                      -                            b                                                                                                                                              =                                  -                                      [                                                                                                                        x                            0                                                    ⁡                                                      (                                                          n                              -                              1                                                        )                                                                          ⁢                                                  A                          1                                                                    +                                                                                                                                                                               ⁢                                                                                                    x                        0                                            ⁡                                              (                                                  n                          -                          2                                                )                                                              ⁢                                          A                      2                                                        +                                                                                    x                        0                                            ⁡                                              (                                                  n                          -                          3                                                )                                                              ⁢                                          A                      3                                                        +                  …                  +                                                                                    x                        0                                            ⁡                                              (                                                  n                          -                          K                                                )                                                              ⁢                                          A                      K                                                                      ]                            +                              [                                                                                                    x                        1                                            ⁡                                              (                                                  n                          -                          1                                                )                                                              ⁢                                          A                      1                                                        +                                                                                                                                                             ⁢                                                                                                              x                          1                                                ⁡                                                  (                                                      n                            -                            2                                                    )                                                                    ⁢                                              A                        2                                                              +                                                                                            x                          1                                                ⁡                                                  (                                                      n                            -                            3                                                    )                                                                    ⁢                                              A                        3                                                              +                    …                    +                                                                                            x                          1                                                ⁡                                                  (                                                      n                            -                            K                                                    )                                                                    ⁢                                              A                        K                                                                              ]                                ⁢                                  2                                      -                    1                                                              +                                                                                         ⁢                              [                                                                                                    x                        2                                            ⁡                                              (                                                  n                          -                          1                                                )                                                              ⁢                                          A                      1                                                        +                                                                                    x                        2                                            ⁡                                              (                                                  n                          -                          2                                                )                                                              ⁢                                          A                      2                                                        +                                                                                    x                        2                                            ⁡                                              (                                                  n                          -                          3                                                )                                                              ⁢                                          A                      3                                                        +                  …                  +                                                                                                                                                             ⁢                                                                                    x                        2                                            ⁡                                              (                                                  n                          -                          K                                                )                                                              ⁢                                          A                      K                                                        ]                                ⁢                                  2                                      -                    2                                                              +                              [                                                                                                    x                        3                                            ⁡                                              (                                                  n                          -                          1                                                )                                                              ⁢                                          A                      1                                                        +                                                                                    x                        3                                            ⁡                                              (                                                  n                          -                          2                                                )                                                              ⁢                                          A                      2                                                        +                                                                                                                                         ⁢                                                                                                    x                        3                                            ⁡                                              (                                                  n                          -                          3                                                )                                                              ⁢                                          A                      3                                                        +                  …                  +                                                                                    x                        3                                            ⁡                                              (                                                  n                          -                          K                                                )                                                              ⁢                                          A                      K                                                                      ]                            ⁢                              2                                  -                  3                                                                                                                       ⁢                              ⋮                ⁢                                                                   +                                                                                                       ⁢                              [                                                                                                    x                                                  B                          -                          1                                                                    ⁡                                              (                                                  n                          -                          1                                                )                                                              ⁢                                          A                      1                                                        +                                                                                    x                                                  B                          -                          1                                                                    ⁡                                              (                                                  n                          -                          2                                                )                                                              ⁢                                          A                      2                                                        +                                                                                    x                                                  B                          -                          1                                                                    ⁡                                              (                                                  n                          -                          3                                                )                                                              ⁢                                          A                      3                                                        +                  …                  +                                                                                                                                         ⁢                                                                            x                                              B                        -                        1                                                              ⁡                                          (                                              n                        -                        K                                            )                                                        ⁢                                      A                    K                                                  ]                            ⁢                              2                                  -                                      (                                          B                      -                      1                                        )                                                                                                          (        3        )            
In the above equation, each row describes a multiplication of all coefficients with all bits at a certain bit position i.e. in row number zero, all least significant bits are multiplied with the corresponding coefficients, and in row B-1, all most significant bits are multiplied with the corresponding coefficients.
After these multiplications have been carried out, the final result is obtained by weighting the rows with the corresponding bit position, and adding all weighted rows together.
However, this prior art solution leads to the following drawbacks:                a) The look-up tables are all identical, and the size of the look-up tables increases exponentially with an increase in the bit number of the input data.        b) The shift operation provided for the final weighting of the different bit positions introduces a latency into the digital filter. This latency is often unacceptable for feedback systems, i.e. IIR filters, since those systems will not work if the input data arrives faster than the end of processing of the previous data. Thus, in order to calculate y(n), the multiplication of x(n−1) with b1 has to be finished before the next sample data x(n) arrives.        